package com.celan.year2023.month01.day03;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Solution {
    public boolean areNumbersAscending(String s) {
        int pre = -1;
        int idx = 0;
        while (idx < s.length()) {
            while (idx < s.length() && !Character.isDigit(s.charAt(idx))) {
                idx++;
            }
            if (idx == s.length() && pre == -1) return false;
            StringBuilder num = new StringBuilder();
            while (idx < s.length() && Character.isDigit(s.charAt(idx))) {
                num.append(s.charAt(idx++));
            }
            if (num.length() != 0) {
                int cur = Integer.parseInt(num.toString());
                if (cur <= pre) return false;
                else pre = cur;
            }
        }
        return true;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        dfs(root);
        return res;
    }

    void dfs(TreeNode root) {
        if (root == null) return;

        if (root.left != null) {
            dfs(root.left);
        }
        res.add(root.val);
        if (root.right != null) {
            dfs(root.right);
        }
    }

    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }

    public boolean isSymmetric(TreeNode root) {
        return isSym(root.left, root.right);
    }

    private boolean isSym(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null) return false;
        if (right == null) return false;
        if (left.val != right.val) return false;

        return isSym(left.left, right.right) && isSym(left.right, right.left);
    }


    public int maxDepth(TreeNode root) {
        return recur(root);
    }

    int recur(TreeNode root) {
        if (root == null) return 0;

        int depth = 1;
        depth += Math.max(recur(root.left), recur(root.right));
        return depth;
    }

    HashMap<Integer, Integer> map;
    int[] preorder;
    int[] inorder;
    int n;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        map = new HashMap<>();
        n = preorder.length;
        for (int i = 0; i < n; i++) {
            map.put(inorder[i], i);
        }
        return build(0, n - 1, 0, n - 1);
    }

    TreeNode build(int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) return null;
        int root_val = preorder[preorder_left];
        if (preorder_left == preorder_right) {
            return new TreeNode(root_val);
        }

        TreeNode root = new TreeNode(root_val);
        int size = map.get(root_val) - inorder_left;
        root.left = build(preorder_left + 1, preorder_left + size, inorder_left, map.get(root_val));//2,1
        root.right = build(preorder_left + size + 1, preorder_right, map.get(root_val) + 1, inorder_right);//null
        return root;
    }
    //[1,2,3]
    //[3,2,1]
    //    1
    //  2  null
    //3  null
}
